package nowcoder;

public class NumberOfOne {
	
	public int NumberOf1Between1AndN_Solution(int n) {
		if(n <= 0)
            return 0;
	    
		int[] dp = new int[n + 1];
		dp[1] = 1;
		for(int i = 2; i <= n; i++) {
			dp[i] = dp[i - 1] + getNumberOfOne(i);
		}
		
		return dp[n - 1];
    }

	private int getNumberOfOne(int number) {
		int res = 0;
		char[] chars = (number + "").toCharArray();
		
		for(int i = 0; i < chars.length; i++) {
			if(chars[i] == '1')
				res++;
		}
		return res;
	}

}
